//题目(困难):
// 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
// 例如 arr = [2,3,4] 的中位数是 3 。
// 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
// 实现 MedianFinder 类:
// MedianFinder() 初始化 MedianFinder 对象。
// void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
// double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
//代码:
class MedianFinder 
{
    //用两个队列来存储数据，front建大根堆,排降序,存前半部分元素;
    priority_queue<int> heap_front;
    //back建小根堆,排升序,存后半部分元素
    priority_queue<int,vector<int>,greater<int>> heap_back;
public:
    MedianFinder() 
    {}
    
    void addNum(int num) 
    {
        if(heap_back.size()<=heap_front.size())
            heap_back.push(num);
        else 
            heap_front.push(num);
        //*核心步骤:元素调整,要保证:heap_front.top()<=heap_back.top()
        while(!heap_front.empty() && !heap_back.empty() && heap_front.top()>heap_back.top())
        {
            heap_back.push(heap_front.top());
            heap_front.push(heap_back.top());
            heap_back.pop();
            heap_front.pop();
        }
    }
    
    double findMedian() 
    {
        //法一：将出队列的元素用一个数组存起来，拿到中位数后，再将元素插回去  （不用想，肯定超时）
        // vector<int> v;
        // double ret;
        // int count=heap.size()/2;
        // if(heap.size()%2==1)//奇数个元素
        // {
        //     //1.出队列，并记录抛出的元素
        //     while(count>0)
        //     {
        //         v.push_back(heap.top());
        //         heap.pop();
        //         count--;
        //     }
        //     ret=heap.top();
        //     //2.将抛出的元素再插入队列
        //     for(const auto& x:v)heap.push(x);
        // }
        // else  //偶数个元素
        // {
        //     //1.出队列，并记录抛出的元素
        //     while(count>0)
        //     {
        //         v.push_back(heap.top());
        //         heap.pop();
        //         count--;
        //     }
        //     ret=(heap.top()+v.back())*1.0/2;
        //     //2.将抛出的元素再插入队列
        //     for(const auto& x:v)heap.push(x);
        // }
        // return ret;

        //法二(双队列法):
        if((heap_back.size()+heap_front.size())%2==1)return heap_back.top();
        else return 1.0*(heap_front.top()+heap_back.top())/2;
    }
};